home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 8195 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.8 KB
  1. Path: anvil.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: REQUEST: Recursive functions
  5. Date: 1 Mar 1996 15:41:15 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4h81urINNuo@anvil.ugrad.cs.ubc.ca>
  8. References: <4h7lft$8ql@cis.clark.edu>
  9. NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca
  10.  
  11. In article <4h7lft$8ql@cis.clark.edu>,
  12. Michael Talmage <michaelt@clark.edu> wrote:
  13. >I need some help to write a recursive function that will move a mouse through
  14. >a maze to find some cheese at the end.  My instructor did not really teach us 
  15. >how to write recursive functions in class.  Any help will be appreciated.  
  16.  
  17. Recursive functions are ones that call themselves. There can also be mutually
  18. recursive functions that call each other.
  19.  
  20. They are good for representing a problem that can be given in terms of itself.
  21. For example, the fibonacci sequence can be defined recursively:
  22.  
  23. fib(n) -- that is, the n-th fibonacci number starting from 0 -- is:
  24.     1 if n is 0;
  25.     1 if n is 1;
  26.     or fib(n-1) + fib(n-2) otherwise.
  27.  
  28. See, the computation of fib(x) requires fib(x-1) or fib(x-2). Recursion has to
  29. _terminate_ somewhere, hence we have conditions for just returning a value.
  30. Thus an explicit solution is given when the problem is recognized to be small
  31. enough.
  32.  
  33. In the C language, a function do compute above might look like this:
  34.  
  35. unsigned long fib(unsigned long n)
  36. {
  37.     switch (n) {
  38.     case 0:
  39.     case 1:
  40.         return 1;
  41.         break;
  42.     default:
  43.         return fib(n-1) + fib(n-2);
  44.         break;
  45.     }
  46.     /* notreached */
  47. }
  48.  
  49. That is how you write a recursive function. In applying it to your problem, you
  50. have to come up with a recursive definition of the problem with the
  51. characteristic that the recursion stops when the solution is recognized (i.e.
  52. you enter the cell of the maze where the cheese is found).
  53.  
  54. Assuming that the maze is based on a square grid, it is isomorphic to a
  55. tertiary tree (a tree with three possibly nil children at each node).
  56.  
  57.                         room_1
  58.                         /  |  \
  59.                      left str right
  60.                     /      \
  61.                   room_2   room_3
  62.                  /  |  \
  63.               left str right
  64.                          \
  65.                         cheese_room
  66.  
  67. The maze is really a tree, where you start at the root and make decisions about
  68. whether to go left, right or straight. Of course, this assumes that the maze
  69. does not contain loops.
  70.  
  71. If the maze does not contain loops, traversing it is identical to a recursive
  72. traversal of the tree. By the way, the above tree might represent the maze:
  73.  
  74.       +-+-+
  75.       |3 1|
  76.       +-+ +
  77.       |C 2|
  78.       +-+-+  initial ``straight'' direction is <-
  79.  
  80. There are other ways to define the problem, which change the representation and
  81. algorithm slightly.
  82. -- 
  83.  
  84.